# 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
# 判断一个树是不是另一个树的子结构，其实有两种情况，一个是B是A的子树，另一个是B是A的包含树

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


def ifBisSubA(treeA, treeB):
    if treeB == None:
        return True
    if treeA == None:
        return False
    if treeA.val == treeB.val:
        return ifBisSubA(treeA.left, treeB.left) and ifBisSubA(treeA.right, treeB.right)
    else:
        return False


def HasSubTree(treeA, treeB):
    if treeB == None or treeA == None:
        return False
    return ifBisSubA(treeA, treeB) or HasSubTree(treeA.left, treeB) or HasSubTree(treeA.right, treeB)
